﻿#pragma once
#include "stdafx.h"

/*
最接近的三数之和 中等难度

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。


 示例：

 输入：nums = [-1,2,1,-4], target = 1
 输出：2
 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
  
  提示：

  3 <= nums.length <= 10^3
  -10^3 <= nums[i] <= 10^3
  -10^4 <= target <= 10^4

  解题思路：这个题目其实就是上个题目3个数相加的变形，采用的方法依旧是双指针法。记录最小值的对应的数
  时间复杂度O(n).
*/

int threeSumClosest(vector<int>& nums, int target) 
{
	sort(nums.begin(),nums.end());  //排序，
	int n = nums.size();
	int best = 1e7;
	// 根据差值的绝对值来更新答案 lambda函数
	auto updata = [&](int cur)
	{
		if (abs(cur - target) < abs(best-target))
		{
			best = cur;
		}
	};

	for (int i =0; i<n; i++)
	{
		// 保证和上一次枚举的元素不相等
		if (i >0 && nums[i] == nums[i-1])
		{
			continue;
		}
		// 使用双指针枚举 b 和 c
		int j = i + 1, k = n - 1;
		while (j < k)
		{
			int sum = nums[i] + nums[j] + nums[k];
			if (sum == target)
			{
				return target;
			}
			updata(sum);
			//当和大于目标值的时候。
			if (sum >target)
			{
				//如果和大于target，移动c 对应指针
				int k0 = k - 1;
				while (j <k0 && nums[k0]==nums[k])
				{
					--k0;
				}
				k = k0;
			}
			else
			{
				int j0 = j + 1;
				//移动到下一个不相等的元素
				while (j0 <k &&nums[j0] ==nums[j])
				{
					++j0;
				}
				j = j0;
			}
		}
	}
	return best;
}








